package lecode;

public class 两两交换链表中的节点24 {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4,new ListNode(5)))));
//        System.out.println(iteratePairs(l1).toString());
        System.out.println(swapPairs(l1).toString());
    }


    /**
     * 迭代法
     *  res - 1     -2      -3    -4
     *  cur   head   next   tmp
     *
     *  res - 2     -1     -3    -4
     *              cur   head   next     tmp
     */
    public static ListNode iteratePairs(ListNode head) {
          if (head == null || head.next == null) {
              return head;
          }
          ListNode res = new ListNode();
          res.next = head;//cur = head
          ListNode cur = res;
          while (cur.next != null && cur.next.next != null) {
              //定义临时变量
              ListNode next = head.next;// next = 2
              ListNode tmp = head.next.next; // tmp = 3
              //交换逻辑
              cur.next = next;// 2->res.next
              next.next = head;//1->2
              head.next = tmp; //head.next = 3  3-1
              //重新指向
              cur = head;//cur = 1
              head =head.next;//head = 3
          }
          return res.next;
    }

    /**
     * 递归法
     *  1   head
     *  2   next
     *  3
     *  4
     */
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;// next = 2,4
        head.next = swapPairs(head.next.next);//{head.next.next =3 ,  把下一个交换后的节点返回来（4）, (4 -> 1.next)},{null -> 3.next  }
        next.next = head;//(1 -> 2) , (3 -> 4.next)
        return next;
    }

}
